package array;

public class _704_二分查找 {
	
	// 二分查找两种区间：左闭右闭[] 左闭右开[)
	/* 左闭右闭
	 * 意味着包含right，所以while循环必须<=right，才能符合区间，比如[1,1]是符合区间的
	 * 在进行区间分割时，应是 r = mid-1 ，因为该mid的值已经经过 arr[mid] == right 判断了，只有不等于才会进入区间分割
	 * 此外，当arr.size = n 时，初始的r应该是n-1，否则会越界，因为最终可能会搜索到这个n-1的位置  
	 * 
	 * 左闭右开，意味着不包含right，所以while循环必须left<right，才能符合区间，比如[1,1)是不符合区间的，1不能既闭又开
	 * 在进行区间分割时，应是 r = mid，因为在接下来的搜素时，是不包含mid这个值的，不会导致该位置重复搜素
	 * 此外，当arr.size = n时，初始的r应该是n，因为是右开，条件是while(left<right)，所以不会搜索到n这个位置，将其作为开区间的值
	 *
	 * 由于两个区间都是左闭，所以区间分割时，都可以采用 left = mid + 1
	 * */
    public static int search(int[] nums, int target) {
    	int left = 0;
    	int right = nums.length - 1;
    	int mid;
    	while(left <= right) {
    		mid = (left + right) / 2;
    		if(nums[mid] == target) {
    			return mid;
    		} else if(target < nums[mid]) {
    			right = mid - 1;
    		} else {
    			left = mid + 1;
    		}
    	}
    	
    	return -1;
    }
    
    public static int search2(int[] nums, int target) {
    	int left = 0;
    	int right = nums.length;
    	int mid;
    	while(left < right) {
    		mid = (left + right) / 2;
    		if(nums[mid] == target) {
    			return mid;
    		} else if(target < nums[mid]) {
    			right = mid;
    		} else {
    			left = mid + 1;
    		}
    	}
    	
    	return -1;
    }
	
	public static void main(String[] args) {
		int nums[] = {1,2,3,6,8,9,23,56};
		System.out.println(search2(nums,1));
	}
}
